The present invention relates to the digital processing of signals and relates more particularly to a circuit able to receive signals representing n digital values x.sub.j so as to produce signals representing n digital coefficients F.sub.v of the form ##EQU1##
This category includes in particular the transformations called "monodimensional cosine transformations" where f(j,v) is of the form EQU cos (2j+1) v/n
These transformations are used in particular for processing images for preparing transmission thereof in digital form.
In this case, from a block of n.times.n digital values, n.times.n coefficients F.sub.v are produced.
To produce these transformations, algorithms are used for example Byeong Gi Lee's algorithm for the monodimensional cosine transform.
Byeong Gi Lee's algorithm is described in the article "FCT - a Fast Cosine Transform", published in the proceedings IEEE ICASSP of 1984.
These algorithms are in the form of graphs indicating the successive operations to be carried out on the data or groups of data which are assumed to arrive in parallel.
Byeong Gi Lee's algorithm is represented by the graph of FIG. 1. The input data to be processed are the digital values X.sub.0 to X.sub.15 (16 values), each coded for example over 16 bits. The output values are the coefficients F0 to F15. The input data are processed in pairs in a first series of operators which each provide two results; the results are again processed in pairs in a second series of operators which in their turn each supply two results, and so on.
In this graph, two sorts of operators are met with, redrawn schematically in FIG. 2; an addition operator causes the values A+B and B to correspond to two values A and B and a so called "butterfly" operator causes the values A+B and C* (A-B) to correspond to two values A and B, where C is a multiplicator coefficient.
To better identify these Operators in FIG. 1, an addition operator has been surrounded with a rectangle and a butterfly operator with another rectangle. The graph of FIG. 1 includes 32 butterfly operators and 17 addition operators.
FIG. 2 also shows two other operators used when it is desired to carry out the inverse transformation of the original transformation, that is to say when it is desired to find again values x.sub.j from coefficients F.sub.v. The operators are respectively a "return" addition operator supplying A+B and A from A and B and a "return" butterfly operator supplying A+c.sub.r B and A-c.sub.r B from A and B.
The architectures of the circuits for carrying out transformations of the cosine type are designed for processing the data in real time, that is to say sufficiently rapidly for the results of the calculation to be supplied with a flow equal to the data flow entering the circuit.
An architecture already proposed consists in forming microprogrammed operators in parallel for simultaneously processing n series of n digital values x.sub.j. Each operator is capable of carrying out very simple operations under the control of a microprogrammed sequencer and the sequence of operations carried out makes it possible to execute the whole of the algorithm over the n series, through an instruction microprogram; all the operators simultaneously receive the same instruction. Beyong Ge Lee's algorithm for processing 16 digital values of 16 bits each requires for example about 500 instructions (addition, transfer from one register to another, shift etc . . . ). A block of lines of 16 values each is processed by 16 operators each assigned to a line of 16 values.
Consequently, in this type of architecture, n non specialized operators are used capable not only of carrying out several types of operations (addition or butterfly, outgoing or return), but also of carrying out these operations over several data appearing successively at the inputs of these operators.
Thus, in the graph of FIG. 1, an operator will execute the butterfly operation over two data x.sub.0 and x.sub.15 then over two other data x.sub.1 and x.sub.14 etc, then when it has finished a series of eight operations, it will begin again on the sixteen results of these operations, that is to say first of all on two data which are on the one hand the result obtained from x.sub.0 and x.sub.15 and on the other hand the result obtained from x.sub.7 and x.sub.13 etc.
FIG. 3 shows how the architecture of such a circuit appears, with a working memory of 16 words and an operator performing successive operations (32 multiplications and 81 additions) on the words of the memory, the operator being controlled by an instruction program delivered by a microprogrammed sequencer (about 500 instructions for executing the transformation over 16 points).
In such an architecture it is necessary to cascade two circuits so as to perform the bidimensional cosine transformation.
In another circuit architecture, the lines of 16 digital values are introduced sequentially, one after the other and, once they are stored, an operator matrix receives the sixteen digital values in parallel. The operators are those shown in FIG. 2, and they are connected together as in the graph of FIG. 1. This is a systolic type architecture where the topology of the circuit is very close to that of the graph. The operators are necessarily "series" operators that is to say working sequentially first of all on the least significant bits of the numbers to be processed, then on the bits of immediately higher significance etc. The 16 digital values are therefore each introduced in the form of sixteen bits entering the operator matrix in series. Each operator processes two well defined data; for example one operator is assigned solely to the execution of a butterfly operation on the data x.sub.0 and x.sub.15, and there will necessarily be other operators for processing the other data and the results of the processing of this data. This is an essential difference with the above described architecture. This systolic type architecture has the advantage of being rapid and compact. But the accuracy of the computations is necessarily limited, the processing of the blocks of a size less than the size normally provided is difficult, and the flexibility and versatility of the circuit are low.
To construct an integrated circuit having very good performances in so far as the speed, the compactness, the versatility and the aptitude to carry out not only the transformation of values x.sub.j into coefficients F.sub.v but also the reverse transformation making it possible to find again the values x.sub.j from the coefficients F.sub.v, the present invention proposes an architecture different from the known architectures.